package dp;

/**
 *  三步走 明确边界 明确dp[][] 含义 明确状态转移方程
 * 状态转移方程需要倒着分析   比如最后一个  怎么由之前状态转移过来
 */
public class  不同路径_62{
                public  int  uniquePaths(int  m,  int  n)  {
                        //  到每个点的路径数量
                        int[][]  dp  =  new  int[m][n];
                        for(int  i  =  0;  i  <  n;  i++)  dp[0][i]  =  1;
                        for(int  j  =  1;  j  <  m;  j++)  dp[j][0]  =  1;
                        for(int  i  =  1;  i<  m  ;  i++)  {
                                for(int  j  =  1;  j<n;  j++)  {
                                        dp[i][j]  =  dp[i-1][j]  +  dp[i][j-1];
                                }
                        }
                        return  dp[m-1][n-1];
                }
        }
